package dp;

/**
 * @author : Rookie
 * @description : 最长公共子序列
 * @date : 2023/7/1
 */
public class LongestCommonSubSequence {

    public static void main(String[] args) {
        int[] arr1 = new int[] {1,3,5,7,9};
        int[] arr2 = new int[] {1,5,6,7};
        int length = getMaxCommonSubSequenceLength(arr1, arr2);
        System.out.println(length);
    }

    private static int getMaxCommonSubSequenceLength(int[] arr1,int[] arr2) {
        /**
         *         dp[i][j]表示以[0，i-1] nums1和[0,j-1]的nums2最长公共子序列的长度
         *         为什么是i-1和j-1,为了初始化方便 如果是[0,i],[0,j]需要初始化第一行和第一列
         */

        int[][] dp = new int[arr1.length + 1][arr2.length + 1];

        for (int i = 1; i <= arr1.length; i++) {
            for (int j = 1; j <= arr2.length; j++) {
                if (arr1[i-1] == arr2[j-1]) {
                    dp[i][j] = dp[i-1][j-1]+1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        Common.print2dArr(dp);
        return dp[arr1.length][arr2.length];
    }
}
